package com.gitee.wsl.ext.array.sort

/**
 * Implementation: Iterative
 * Space Complexity: O(n)
 * Ease of Use: Natural fit for linked lists
 * Stability: Stable
 * Performance: O(n log n)
 * Memory Usage: O(n), no recursion stack
 */
fun<T : Comparable<T>> Array<T>.bottomUpMergeSort(){
    val size = this.size
    val tempArray = this.copyOf()

    var width = 1
    while (width < size) {
        var i = 0
        while (i < size) {
            // Find the middle point
            val middle = kotlin.math.min(i + width, size)
            // Find the end of the current segment
            val end = kotlin.math.min(i + 2 * width, size)
            // Merge the sub-arrays array[i…middle-1] and array[middle…end-1] into tempArray
            merge(this, tempArray, i, middle, end)
            i += 2 * width
        }
        // Copy the merged array back to the original array
        tempArray.copyInto(this)
        width *= 2
    }
}

/**
 * Merge two sub-arrays of array[].
 *
 * @param array the array to be sorted
 * @param tempArray the temporary array used for merging
 * @param start the start index of the first sub-array
 * @param middle the end index of the first sub-array
 * @param end the end index of the second sub-array
 * @param <T> the type of elements in the array
 * @return the merged array
 */
private fun <T : Comparable<T>> merge(
    array: Array<T>,
    tempArray: Array<T>,
    start: Int,
    middle: Int,
    end: Int,
) {
    var i = start
    var j = middle
    var k = start

    // Merge the two sub-arrays into tempArray
    while (i < middle && j < end) {
        if (array[i] <= array[j]) {
            tempArray[k] = array[i]
            i++
        } else {
            tempArray[k] = array[j]
            j++
        }
        k++
    }

    // Copy remaining elements of the left half, if any
    while (i < middle) {
        tempArray[k] = array[i]
        i++
        k++
    }

    // Copy remaining elements of the right half, if any
    while (j < end) {
        tempArray[k] = array[j]
        j++
        k++
    }
}